// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-26 21:08
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.GraphyTrain;

import java.util.LinkedList;
import java.util.Queue;

public class Connect {
    // 实现对完全二叉树指针的实例化
    // 树的层次遍历获取树的节点和每层的最后一个节点信息
    public Node connect(Node root) {
        // 两个队列交替使用
        Queue<Node> p = new LinkedList<>();
        Queue<Node> q = new LinkedList<>();

        if (root == null) {
            return null;
        }
        root.next = null;
        p.offer(root);
        Node t = root;

        while (!p.isEmpty()) {
            Node pre = null;
            while (!p.isEmpty()) {
                t = p.poll();
                if (pre != null) {
                    pre.next = t;
                }
                if (t.left != null) {
                    q.offer(t.left);
                    q.offer(t.right);
                }
                pre = t;
            }
            t.next = null;  // 每一层的最后一个节点

            pre = null;
            while (!q.isEmpty()) {
                t = q.poll();
                if (pre != null) {
                    pre.next = t;
                }
                if (t.left != null) {
                    p.offer(t.left);
                    p.offer(t.right);
                }
                pre = t;
            }
            t.next = null;  // 每一层的最后一个节点
        }
        return root;
    }

    // Definition for a TreeNode.
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }


}
